package sort.cmp;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author kaho
 * @create 2020/11/26
 */
public class 堆排序 {

    public static int[] heapSort1(int[] arr) {

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparing(v -> v));
        for (int i : arr) {
            pq.offer(i);
        }

        for (int i = 0; i < arr.length && !pq.isEmpty(); i++) {
            arr[i] = pq.poll();
        }

        return arr;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{19, 14, 5, 7, 8, 1};
        int[] ints = heapSort(arr);
    }


    public static int[] heapSort(int[] arr) {
        int length = arr.length;
        for (int i = (arr.length >> 1) - 1; i >= 0; i--) {
            siftDown(arr, i, length);
        }
        while (length > 1) {
            int tmp = arr[--length];
            arr[length] = arr[0];
            arr[0] = tmp;

            siftDown(arr, 0, length);
        }
        return arr;
    }

    private static void siftDown(int[] arr, int targetIdx, int heapSize) {
        int target = arr[targetIdx];
        while (targetIdx < (heapSize >> 1)) {
            int childIdx = (targetIdx << 1) + 1;
            int child = arr[childIdx];

            int rightIdx = childIdx + 1;
            if (rightIdx < heapSize && child < arr[rightIdx]) {
                child = arr[rightIdx];
                childIdx = rightIdx;
            }

            if (target > child) {
                break;
            }
            arr[targetIdx] = child;
            targetIdx = childIdx;
        }
        arr[targetIdx] = target;
    }

}
